// 给定一个包含n+1个整数的数组nums，里边包含的值都在1-n之间，假设nums中只存在一个重复的整数，要求找出这个重复的数
// 要求使用空间复杂度为常数级，时间复杂度小于O(n平方)的解决方法

// 思路，二分查找的思路，对区间【1，n】进行二分，left = 1， right = n，mid为中间数
// 遍历nums，统计小于等于mid的数的数量cnt
// 如果cnt <= mid，重复数一定在右侧，不在左侧，left = mid + 1
// 如果cnt > mid，重复数肯定出现在左侧，right = mid


function findDuplicate(nums) {
    let n = nums.length
    let left = 1
    let right = n
    while (left < right) {
        let mid = Math.floor((right - left) / 2) + left
        let cnt = 0
        for (let i = 0; i < nums.length; i++) {
            if (nums[i] <= mid) {
                cnt++
            }
        }
        if (cnt <= mid) {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}

let arr = [8,9,1, 2, 2,3,,4,5,6,7, 10]
console.log(findDuplicate(arr))